package cz.cvut.kadledav.paa.knapsack.tasks;

import cz.cvut.kadledav.paa.knapsack.bo.Item;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * User: David Kadlecek
 * Date: 2.10.13
 */
public class DynamicProgramingByCostTask extends ATask{

    private static int INVALID_VALUE = -1;

    protected int[] prices;
    protected int[] weights;

    int[][] table;

    private boolean isValid(int leftValue) {
        return leftValue!=INVALID_VALUE;
    }

    public void compute(){
        int maxPriceRange = 0;
        for (int i = 0; i < prices.length; i++) {
            maxPriceRange+=prices[i];
        }
        table = new int[maxPriceRange][prices.length];
        for (int item = 0; item < prices.length; item++) {
            for (int i = 0; i < maxPriceRange; i++) {
                int price = prices[item];
                int weight = weights[item];
                if(item == 0){
                    table[i][0] = i < price ? weight :INVALID_VALUE;
                    continue;
                }
                int leftValue = table[i][item - 1];
                if(i < price) {   // cannot evaluate operation i - price
                    if(isValid(leftValue)){
                        table[i][item] = Math.min(weight,leftValue);
                    } else {
                        table[i][item] = weight;
                    }
                } else {
                    int valueWithoutActual = table[i - price][item - 1];
                    if(!isValid(valueWithoutActual)){  // cannot do anything better
                        table[i][item] = INVALID_VALUE;
                        continue;
                    }
                    if(isValid(leftValue)){
                        table[i][item] = Math.min(valueWithoutActual +weight,leftValue);
                    } else {
                        table[i][item] = valueWithoutActual +weight;
                    }
                }
            }
        }
        maxPrice = findBest();
//        printTable();
//        System.out.println("max price" + maxPrice);
    }

    private int findBest() {
        for (int i = table.length-1; i >= 0 ; i--) {
            if(table[i][prices.length - 1] <= maxAllowedWeight){
                return i+1;
            }
        }
        return 0;
    }


    private void printTable() {
        for (int i = table.length-1; i >= 0 ; i--) {
            StringBuilder sb = new StringBuilder(String.format("%02d : -1 ",i+1));
            for (int item = 0; item < prices.length; item++) {
                sb.append(String.format(" %02d ",table[i][item]));
            }
            System.out.println(sb.toString());
        }
    }

    public void setItems(List<Item> items) {
        prices = new int[items.size()];
        weights = new int[items.size()];
        for (int i = 0; i < items.size(); i++) {
            prices[i] = items.get(i).getPrice();
            weights[i] = items.get(i).getWeight();
        }
    }

    private Set<Integer> resolveVectorFrom(int price, int rightTop) {
        HashSet<Integer> take = new HashSet<>();
        for (int item = rightTop; item >= 0; item--) {
            if(price < 0 || item < 0){
                return take;
            }
            if(item == 0){
                take.add(item);
                return take;
            }
            int leftValue = table[price][item - 1];
            if(isValid(leftValue) && leftValue <= table[price][item]) {
                continue;
            }
            take.add(item);
            price = price - prices[item];
        }
        return take;
    }

    public Set<Integer> getComputedItemsIds() {
        for (int i = table.length-1; i >= 0 ; i--) {
            if(table[i][prices.length - 1] <= maxAllowedWeight){
                return resolveVectorFrom(i,prices.length - 1);  //best position
            }
        }
        throw new RuntimeException("Best solution was not found");
    }
}
